package 力扣_滑动窗口;

/**
 * @author zx
 * @create 2022-05-17 21:10
 */
public class 最小覆盖子串_76 {
    public String minWindow(String s, String t) {
        int[] hash = new int[128];
        for (int i = 0; i < t.length(); i++) {
            hash[t.charAt(i)]++;
        }
        //size记录窗口大小,count是需求的字符个数,start是最小覆盖串开始的index
        int left = 0, size = Integer.MAX_VALUE, count = t.length(), start = 0;
        for(int right = 0;right < s.length();right++){
            if (hash[s.charAt(right)] > 0) {//需要此字符
                count--;
            }
            hash[s.charAt(right)]--;//把右边的字符加入窗口？？？这里比较难理解？？？
            if(count == 0){//count == 0：窗口中已经包含所有字符
                while (hash[s.charAt(left)] < 0) {
                    hash[s.charAt(left)]++;//释放左边移动出窗口的字符
                    left++;
                }
                if (right - left + 1 < size) {//不能右移时候更新最小窗口大小,更新最小窗口的start
                    size = right - left + 1;
                    start = left;//记录下最小值时候的开始位置,最后返回覆盖串时候会用到
                }
            }
        }
        return size == Integer.MAX_VALUE ? "" : s.substring(start, start + size);
    }
}
